package leetcode.d_1_99;

public class P45JumpGame2{
    public static void main(String[] args) {
        P45JumpGame2.Solution solution = new P45JumpGame2().new Solution();
        int[] nums1 = {2,3,1,1,4};
        int[] nums2 = {2,3,0,1,4};
        System.out.println(solution.jump(nums1));
        System.out.println(solution.jump(nums2));
    }

    class Solution {
        public int jump(int[] nums) {
            int steps = 0;
            int maxPos = 0;
            int end = 0;
            for (int i=0; i < nums.length-1; i++) {
                maxPos = Math.max(maxPos, i + nums[i]);
                if (end == i) {
                    steps++;
                    end = maxPos;
                }
            }
            return steps;
        }
    }
}
